package leetcode_800;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 *@author 周杨
 *AccountsMerge_721 给定N个账户 和邮件 合并这些账号
 *describe: 用并查集 AC 35%
 *2018年10月12日 下午3:34:27
 */
public class AccountsMerge_721 {
	
	/**
	 * describe:用并查集
	 * 2018年10月12日 下午3:34:18
	 */
	public List<List<String>> accountsMerge(List<List<String>> acts) {
        Map<String, String> owner = new HashMap<>();
        Map<String, String> parents = new HashMap<>();
        Map<String, TreeSet<String>> unions = new HashMap<>();
        for (List<String> a : acts) {
            for (int i = 1; i < a.size(); i++) {
                parents.put(a.get(i), a.get(i));
                owner.put(a.get(i), a.get(0));
            }
        }
        for (List<String> a : acts) {
            String p = find(a.get(1), parents);
            for (int i = 2; i < a.size(); i++)
                parents.put(find(a.get(i), parents), p);
        }
        for(List<String> a : acts) {
            String p = find(a.get(1), parents);
            if (!unions.containsKey(p)) unions.put(p, new TreeSet<>());
            for (int i = 1; i < a.size(); i++)
                unions.get(p).add(a.get(i));
        }
        List<List<String>> res = new ArrayList<>();
        for (String p : unions.keySet()) {
            List<String> emails = new ArrayList(unions.get(p));
            emails.add(0, owner.get(p));
            res.add(emails);
        }
        return res;
    }
    private String find(String s, Map<String, String> p) {
        return p.get(s) == s ? s : find(p.get(s), p);
    }
	
	/**
	 * describe:思想错误 前面如果账户没有关联 但是突然出现一个账户连接两个账户 那么就没办法处理
	 * 2018年10月12日 下午3:33:26
	 */
	public List<List<String>> accountsMerge1(List<List<String>> accounts) {
        Map<String,Integer>mailMap=new HashMap<String,Integer>();
        for(int i=0;i<accounts.size();++i) {
        	List<String> account=accounts.get(i);
        	for(int j=1;j<account.size();++j) {
        		String email=account.get(j);
        		Integer index=mailMap.get(email);
        		if(index==null) {//此人并未被注册
        			mailMap.put(email, i);
        		}
        		else {//发现同名的账户 那么不用再检查了 把该用户的所有邮件并入该同名账户中
        			if(index==i)
        				continue;
        			for(int k=1;k<account.size();++k) {
        				mailMap.put(account.get(k), index);//绝不可能再出现重名 index是唯一的
        			}
        			break;//进行下一个用户的判断
        		}
        	}
        }
        List<List<String>> res=new ArrayList<List<String>>();
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        //map记录了匹配的记录 
        for(Map.Entry<String, Integer> entry:mailMap.entrySet()) {
        	int index=entry.getValue();
        	Integer mapIndex=map.get(index);
        	if(mapIndex==null) {//还没有收录进入
        		List<String> now=new ArrayList<String>();
        		now.add(accounts.get(index).get(0));//名字先填入
        		now.add(entry.getKey());//填入邮件
        		res.add(now);
        		map.put(index, res.size()-1);
        	}
        	else {
        		List<String> now=res.get(mapIndex);
        		now.add(entry.getKey());
        	}
        }
        List<List<String>> fin=new ArrayList<List<String>>();
        for(List<String> list:res) {//进行邮件排序
        	List<String> now=new ArrayList<String>();
        	now.add(list.get(0));//名字
        	Set<String> treeSet=new TreeSet<String>();
        	for(int j=1;j<list.size();++j) {
        		treeSet.add(list.get(j));
        	}
        	now.addAll(treeSet);
        	fin.add(now);
        }
        return fin;
    }
}
